#pragma once
#include<iostream>
using namespace std;
#include<string.h>
#include<assert.h>

typedef char VertexType[50];
typedef int WeightType;
#define NUMMAX 50
#define CONSTMAX  1000

struct MGraph
{
	WeightType arcs[NUMMAX][NUMMAX];
	VertexType vers[NUMMAX];
	int vexNum;
	int arcNum;
};

void MGraphCreate(MGraph& G);

void MGraphDisp(const MGraph& G);

struct ArcNode
{
	int vexi;
	WeightType info;
	ArcNode* next;
};
struct VexNode
{
	VertexType vertex;
	ArcNode* firstArc;
};
struct ALGraph
{
	VexNode adjlist[NUMMAX];
	int vexNum;
	int arcNum;
};
void ChangeMGraphToALGraph(ALGraph& ALG, const MGraph& MG);
void ALGraphDisp(const ALGraph& G);

void MGraphDFS(const MGraph& G,int v);
void MGraphBFS(const MGraph& G, int v);

struct LowCost
{
	int weight;
	int adjNodeNo;
};

void MGraphPrim(const MGraph& G, int v,LowCost lowcost[]);

struct Dist
{
	int distance;
	int path;
};
void MGraphDijstra(const MGraph& G, int v, Dist dist[]);


typedef int QDataType;
struct QueueNode
{
	QDataType _data;
	QueueNode* _next;
};
class Queue
{
public:
	Queue()
	{
		_front = _rear = NULL;
		_size = 0;
	}
	void Push(const QDataType& x)
	{
		QueueNode* s = NewNode(x);
		if (_front == NULL)
		{
			_front = _rear = s;
		}
		else
		{
			_rear->_next = s;
			_rear = s;
		}
		_size++;
	}
	int Empty()
	{
		return !(_size);
	}
	void Pop()
	{
		assert(!Empty());
		if (_front == _rear)
		{
			free(_front);
			_front = _rear = NULL;
		}
		else
		{
			QueueNode* next;
			next = _front->_next;
			free(_front);
			_front = next;
		}
		_size--;
	}
	QDataType Front()
	{
		assert(!Empty());
		return _front->_data;
	}

private:
	QueueNode* NewNode(const QDataType& x)
	{
		QueueNode* s = (QueueNode*)malloc(sizeof(QueueNode));
		if (s == NULL)
		{
			perror("malloc fail::");
			return NULL;
		}
		s->_data = x;
		s->_next = NULL;
		return s;
	}

	QueueNode* _front;
	QueueNode* _rear;
	int _size;
};